import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

//重写compareTo方法，创建大根堆
class IntCmp implements Comparator<Integer> {
    public int compare(Integer o1, Integer o2){
        return o2.compareTo(o1);
    }
}

public class Test {

    public static int[] smallestK(int[]arr, int k){
        int[] ret = new int[k];
        //如果数组为空或者输入的k值不合法，则报错
        if(arr == null || k <= 0){
            System.out.println("输入有误，请重新输入！");
            return ret;
        }
        PriorityQueue<Integer> pq = new PriorityQueue<>(new IntCmp());
        //利用前k个元素建立大根堆
        for (int i = 0; i < k; i++) {
            pq.offer(arr[i]);
        }

        //遍历剩下的n-k个元素，与堆顶元素相比较
        int len = arr.length;
        for (int i = k; i < len; i++) {
            int peekVal = pq.peek();
            //如果该元素小于堆顶的元素，则删除堆顶元素，将该元素入堆
            if(peekVal > arr[i]){
                pq.poll();
                pq.offer(arr[i]);
            }
        }

        //此时优先权队列中的k个元素即为所求
        for (int i = 0; i < k; i++) {
            ret[i] = pq.poll();
        }

        return ret;
    }
    public static void main(String[] args) {
        //输入要比较的元素个数
        Scanner in = new Scanner(System.in);
        System.out.println("输入要比较的元素个数：");
        int n = in.nextInt();
        System.out.println("k的值为：");
        int k = in.nextInt();

        //输入要比较的一组数
        System.out.println("输入要比较的数据：");
        int[] tmp = new int[n];
        for (int i = 0; i < n; i++) {
            tmp[i] = in.nextInt();
        }

        System.out.println("前" + k + "个最小值为：");
        int[] ret = smallestK(tmp, k);
        for (int i = 0; i < k; i++) {
            System.out.print(ret[i] + " ");
        }
    }
}
